/*++ Module: Stacks, Linked Lists, and Queues Programming Assignment #1 CSE 373 2000 Winter Quarter University of Washington Description: This module implements a simple stack, queue, and linked list demonstration program. There are five basic parts to this program. 1. A command line interpreter routine called GetNextCommand that reads in and decodes each new input line. The routine is responsible for determine the type of command entered and optionally decoding any specified integer input value. This module is setup to read from stdin 2. A set of stack routines to create and manipulate a stack of integers 3. A set of queue routines to create and manipluate a queue of integers 4. A set of linked list routines to create and manipulate a circular doubly linked list of integers 5. A main program responsible for calling the command line interpreter and then processing each command using the appropriate stack, queue, or linked list routine Author: Gary Kimura [GaryKi@cs.washington.edu] 15-Jan-2000 Revision History: --*/ #include #include // // Some basic types that make boolean logic and pointers a bit easier to // understand // #define BOOLEAN char #define PBOOLEAN *BOOLEAN #define TRUE 1 #define FALSE 0 #define NULL ((void *)0) // // We will use the following enumeration to help track the type of command // specified by the user // typedef enum { NEW_STACK, NEW_QUEUE, NEW_LINKEDLIST, DUMP_STACK, DUMP_QUEUE, DUMP_LINKDLIST, PUSH_NUMBER, ENQUEUE_TAIL_NUMBER, INSERT_FRONT_NUMBER, PUSH_ACCUMULATOR, ENQUEUE_TAIL_ACCUMULATOR, INSERT_FRONT_ACCUMULATOR, ENQUEUE_HEAD_NUMBER, INSERT_BACK_NUMBER, ENQUEUE_HEAD_ACCUMULATOR, INSERT_BACK_ACCUMULATOR, TOP_EQUAL, TAIL_EQUAL, FRONT_EQUAL, TOP_PLUS, TAIL_PLUS, FRONT_PLUS, TOP_MINUS, TAIL_MINUS, FRONT_MINUS, TOP_TIMES, TAIL_TIMES, FRONT_TIMES, TOP_DIVIDE, TAIL_DIVIDE, FRONT_DIVIDE, HEAD_EQUAL, BACK_EQUAL, HEAD_PLUS, BACK_PLUS, HEAD_MINUS, BACK_MINUS, HEAD_TIMES, BACK_TIMES, HEAD_DIVIDE, BACK_DIVIDE, POP_EQUAL, DEQUEUE_TAIL_EQUAL, REMOVE_FRONT_EQUAL, POP_PLUS, DEQUEUE_TAIL_PLUS, REMOVE_FRONT_PLUS, POP_MINUS, DEQUEUE_TAIL_MINUS, REMOVE_FRONT_MINUS, POP_TIMES, DEQUEUE_TAIL_TIMES, REMOVE_FRONT_TIMES, POP_DIVIDE, DEQUEUE_TAIL_DIVIDE, REMOVE_FRONT_DIVIDE, DEQUEUE_HEAD_EQUAL, REMOVE_BACK_EQUAL, DEQUEUE_HEAD_PLUS, REMOVE_BACK_PLUS, DEQUEUE_HEAD_MINUS, REMOVE_BACK_MINUS, DEQUEUE_HEAD_TIMES, REMOVE_BACK_TIMES, DEQUEUE_HEAD_DIVIDE, REMOVE_BACK_DIVIDE, REVERSE_STACK, REVERSE_QUEUE, REVERSE_LINKEDLIST, COPY_STACK_TO_QUEUE, COPY_QUEUE_TO_STACK, COPY_LINKEDLIST_TO_STACK, COPY_STACK_TO_LINKEDLIST, COPY_QUEUE_TO_LINKEDLIST, COPY_LINKEDLIST_TO_QUEUE, END_OF_FILE, ILLEGAL_COMMAND } COMMAND_TYPE; // // Procedure prototype for the routine to read in the next command // COMMAND_TYPE GetNextCommand ( int *Param ); // // The stack data type and its operations // typedef struct _STACK { // // The index for the current top of the stack and the total number of // integers allocated to the stack // int Top; int Size; // // A pointer to an array of integers used to store the stack data // int *Array; } STACK, *PSTACK; void NewStack ( PSTACK Stack, int Size ); void DumpStack ( PSTACK Stack ); void PushStack ( PSTACK Stack, int Value ); int PopStack ( PSTACK Stack, BOOLEAN RemoveItem ); void ReverseStack ( PSTACK Stack ); // // The queue data type and its operations // typedef struct _QUEUE { // // The head and tail for the queue are unsigned longs that will be able // to hold quite a large ranges of values before over or under flowing // unsigned long Head; unsigned long Tail; // // The maximum number of integers the queue can hold and the current // number occupied // int Size; int Count; // // A pointer to an array of integers used to store the queue data // int *Array; } QUEUE, *PQUEUE; void NewQueue ( PQUEUE Queue, int Size ); void DumpQueue ( PQUEUE Queue ); // // An enumerated type used to denote which end of the queue to work on // typedef enum _QUEUE_END { HeadOfQueue, TailOfQueue } QUEUE_END, *PQUEUE_END; void EnQueue ( PQUEUE Queue, QUEUE_END QueueEnd, int Value ); int DeQueue ( PQUEUE Queue, QUEUE_END QueueEnd, BOOLEAN RemoveItem ); void ReverseQueue ( PQUEUE Queue ); // // // The linkedlist data type and its operations // // // This is the definition of each entry in the linked list. It is a circular // doubly linked list containing one data item, an integer value // typedef struct _LINKED_LIST_ENTRY { // // Forward and backward pointers for the linked list // struct _LINKED_LIST_ENTRY *Flink; struct _LINKED_LIST_ENTRY *Blink; // // Its data item // int Value; } LINKED_LIST_ENTRY, *PLINKED_LIST_ENTRY; // // The actual linked list data type used by anyone who wants to create and // manipulate linked lists // typedef struct _LINKED_LIST { LINKED_LIST_ENTRY ListHead; } LINKED_LIST, *PLINKED_LIST; void NewLinkedList ( PLINKED_LIST LinkedList ); void DumpLinkedList ( PLINKED_LIST LinkedList ); // // An enumerated type used to denote which end of the linkedlist to work on // typedef enum _LINKED_LIST_END { FrontOfLinkedList, BackOfLinkedList } LINKED_LIST_END, *PLINKED_LIST_END; void InsertLinkedList ( PLINKED_LIST LinkedList, LINKED_LIST_END LinkedListEnd, int Value ); int RemoveLinkedList ( PLINKED_LIST LinkedList, LINKED_LIST_END LinkedListEnd, BOOLEAN RemoveItem ); void ReverseLinkedList ( PLINKED_LIST Linkedlist ); void main( ) /*++ Routine Description: This is the start routine for this program. Its basic logic is to loop constantly calling GetNextCommand until the input file is exhausted. For every command it gets it then calls the appropriate support routine. This module also maintains the accumulator. Arguments: None Return Value: None --*/ { int i; // // Local variables used to get the next command and its parameter // COMMAND_TYPE cmd; int Param; // // Local accumulator that we'll use as needed // int Accumulator = 0; // // This program only uses a single instance of each possible data type // STACK Stack; QUEUE Queue; LINKED_LIST LinkedList; // // Initialize the data types so that when we need to (re)create each // new type it won't thing there is an old one that needs to be // cleaned up after // Stack.Array = NULL; Queue.Array = NULL; LinkedList.ListHead.Flink = NULL; LinkedList.ListHead.Blink = NULL; // // The main logic of the routine is to get and proces the next input // command inside of a big loop which terminates when the eof is reached // This routine keeps track of the accumulator and contains variables // for each of the main types // do { // // Get the next input command and optional parameter // Param = 0; cmd = GetNextCommand( &Param ); // // Now case on the to type of command // switch ( cmd ) { case END_OF_FILE: break; case NEW_STACK: NewStack( &Stack, Param ); break; case DUMP_STACK: DumpStack( &Stack ); break; case PUSH_NUMBER: PushStack( &Stack, Param ); break; case PUSH_ACCUMULATOR: PushStack( &Stack, Accumulator ); break; case TOP_EQUAL: Accumulator = PopStack( &Stack, FALSE ); break; case TOP_PLUS: Accumulator += PopStack( &Stack, FALSE ); break; case TOP_MINUS: Accumulator -= PopStack( &Stack, FALSE ); break; case TOP_TIMES: Accumulator *= PopStack( &Stack, FALSE ); break; case TOP_DIVIDE: Accumulator /= PopStack( &Stack, FALSE ); break; case POP_EQUAL: Accumulator = PopStack( &Stack, TRUE ); break; case POP_PLUS: Accumulator += PopStack( &Stack, TRUE ); break; case POP_MINUS: Accumulator -= PopStack( &Stack, TRUE ); break; case POP_TIMES: Accumulator *= PopStack( &Stack, TRUE ); break; case POP_DIVIDE: Accumulator /= PopStack( &Stack, TRUE ); break; case NEW_QUEUE: NewQueue( &Queue, Param ); break; case DUMP_QUEUE: DumpQueue( &Queue ); break; case ENQUEUE_TAIL_NUMBER: EnQueue( &Queue, TailOfQueue, Param ); break; case ENQUEUE_TAIL_ACCUMULATOR: EnQueue( &Queue, TailOfQueue, Accumulator ); break; case ENQUEUE_HEAD_NUMBER: EnQueue( &Queue, HeadOfQueue, Param ); break; case ENQUEUE_HEAD_ACCUMULATOR: EnQueue( &Queue, HeadOfQueue, Accumulator ); break; case TAIL_EQUAL: Accumulator = DeQueue( &Queue, TailOfQueue, FALSE ); break; case TAIL_PLUS: Accumulator += DeQueue( &Queue, TailOfQueue, FALSE ); break; case TAIL_MINUS: Accumulator -= DeQueue( &Queue, TailOfQueue, FALSE ); break; case TAIL_TIMES: Accumulator *= DeQueue( &Queue, TailOfQueue, FALSE ); break; case TAIL_DIVIDE: Accumulator /= DeQueue( &Queue, TailOfQueue, FALSE ); break; case HEAD_EQUAL: Accumulator = DeQueue( &Queue, HeadOfQueue, FALSE ); break; case HEAD_PLUS: Accumulator += DeQueue( &Queue, HeadOfQueue, FALSE ); break; case HEAD_MINUS: Accumulator -= DeQueue( &Queue, HeadOfQueue, FALSE ); break; case HEAD_TIMES: Accumulator *= DeQueue( &Queue, HeadOfQueue, FALSE ); break; case HEAD_DIVIDE: Accumulator /= DeQueue( &Queue, HeadOfQueue, FALSE ); break; case DEQUEUE_TAIL_EQUAL: Accumulator = DeQueue( &Queue, TailOfQueue, TRUE ); break; case DEQUEUE_TAIL_PLUS: Accumulator += DeQueue( &Queue, TailOfQueue, TRUE ); break; case DEQUEUE_TAIL_MINUS: Accumulator -= DeQueue( &Queue, TailOfQueue, TRUE ); break; case DEQUEUE_TAIL_TIMES: Accumulator *= DeQueue( &Queue, TailOfQueue, TRUE ); break; case DEQUEUE_TAIL_DIVIDE: Accumulator /= DeQueue( &Queue, TailOfQueue, TRUE ); break; case DEQUEUE_HEAD_EQUAL: Accumulator = DeQueue( &Queue, HeadOfQueue, TRUE ); break; case DEQUEUE_HEAD_PLUS: Accumulator += DeQueue( &Queue, HeadOfQueue, TRUE ); break; case DEQUEUE_HEAD_MINUS: Accumulator -= DeQueue( &Queue, HeadOfQueue, TRUE ); break; case DEQUEUE_HEAD_TIMES: Accumulator *= DeQueue( &Queue, HeadOfQueue, TRUE ); break; case DEQUEUE_HEAD_DIVIDE: Accumulator /= DeQueue( &Queue, HeadOfQueue, TRUE ); break; case NEW_LINKEDLIST: NewLinkedList( &LinkedList ); break; case DUMP_LINKDLIST: DumpLinkedList( &LinkedList ); break; case INSERT_FRONT_NUMBER: InsertLinkedList( &LinkedList, FrontOfLinkedList, Param ); break; case INSERT_FRONT_ACCUMULATOR: InsertLinkedList( &LinkedList, FrontOfLinkedList, Accumulator ); break; case INSERT_BACK_NUMBER: InsertLinkedList( &LinkedList, BackOfLinkedList, Param ); break; case INSERT_BACK_ACCUMULATOR: InsertLinkedList( &LinkedList, BackOfLinkedList, Accumulator ); break; case FRONT_EQUAL: Accumulator = RemoveLinkedList( &LinkedList, FrontOfLinkedList, FALSE ); break; case FRONT_PLUS: Accumulator += RemoveLinkedList( &LinkedList, FrontOfLinkedList, FALSE ); break; case FRONT_MINUS: Accumulator -= RemoveLinkedList( &LinkedList, FrontOfLinkedList, FALSE ); break; case FRONT_TIMES: Accumulator *= RemoveLinkedList( &LinkedList, FrontOfLinkedList, FALSE ); break; case FRONT_DIVIDE: Accumulator /= RemoveLinkedList( &LinkedList, FrontOfLinkedList, FALSE ); break; case BACK_EQUAL: Accumulator = RemoveLinkedList( &LinkedList, BackOfLinkedList, FALSE ); break; case BACK_PLUS: Accumulator += RemoveLinkedList( &LinkedList, BackOfLinkedList, FALSE ); break; case BACK_MINUS: Accumulator -= RemoveLinkedList( &LinkedList, BackOfLinkedList, FALSE ); break; case BACK_TIMES: Accumulator *= RemoveLinkedList( &LinkedList, BackOfLinkedList, FALSE ); break; case BACK_DIVIDE: Accumulator /= RemoveLinkedList( &LinkedList, BackOfLinkedList, FALSE ); break; case REMOVE_FRONT_EQUAL: Accumulator = RemoveLinkedList( &LinkedList, FrontOfLinkedList, TRUE ); break; case REMOVE_FRONT_PLUS: Accumulator += RemoveLinkedList( &LinkedList, FrontOfLinkedList, TRUE ); break; case REMOVE_FRONT_MINUS: Accumulator -= RemoveLinkedList( &LinkedList, FrontOfLinkedList, TRUE ); break; case REMOVE_FRONT_TIMES: Accumulator *= RemoveLinkedList( &LinkedList, FrontOfLinkedList, TRUE ); break; case REMOVE_FRONT_DIVIDE: Accumulator /= RemoveLinkedList( &LinkedList, FrontOfLinkedList, TRUE ); break; case REMOVE_BACK_EQUAL: Accumulator = RemoveLinkedList( &LinkedList, BackOfLinkedList, TRUE ); break; case REMOVE_BACK_PLUS: Accumulator += RemoveLinkedList( &LinkedList, BackOfLinkedList, TRUE ); break; case REMOVE_BACK_MINUS: Accumulator -= RemoveLinkedList( &LinkedList, BackOfLinkedList, TRUE ); break; case REMOVE_BACK_TIMES: Accumulator *= RemoveLinkedList( &LinkedList, BackOfLinkedList, TRUE ); break; case REMOVE_BACK_DIVIDE: Accumulator /= RemoveLinkedList( &LinkedList, BackOfLinkedList, TRUE ); break; case REVERSE_STACK: ReverseStack( &Stack ); break; case REVERSE_QUEUE: ReverseQueue( &Queue ); break; case REVERSE_LINKEDLIST: ReverseLinkedList( &LinkedList ); break; case COPY_STACK_TO_QUEUE: NewQueue( &Queue, Queue.Size ); for (i = 0; i <= Stack.Top; i += 1) { EnQueue( &Queue, HeadOfQueue, Stack.Array[i] ); } break; case COPY_STACK_TO_LINKEDLIST: NewLinkedList( &LinkedList ); for (i = 0; i < Stack.Top; i += 1) { InsertLinkedList( &LinkedList, FrontOfLinkedList, Stack.Array[i] ); } break; case COPY_QUEUE_TO_STACK: NewStack( &Stack, Stack.Size ); for (i = 0; i < Queue.Count; i += 1) { PushStack( &Stack, Queue.Array[(Queue.Head + i) % Queue.Size] ); } break; case COPY_QUEUE_TO_LINKEDLIST: NewLinkedList( &LinkedList ); for (i = 0; i < Queue.Count; i += 1) { InsertLinkedList( &LinkedList, BackOfLinkedList, Queue.Array[(Queue.Head + i) % Queue.Size] ); } break; case COPY_LINKEDLIST_TO_STACK: NewStack( &Stack, Stack.Size ); { PLINKED_LIST_ENTRY Entry; for (Entry = LinkedList.ListHead.Flink; Entry != &LinkedList.ListHead; Entry = Entry->Flink) { PushStack( &Stack, Entry->Value ); } } break; case COPY_LINKEDLIST_TO_QUEUE: printf("copy linkedlist to queue\n"); break; NewQueue( &Queue, Queue.Size ); { PLINKED_LIST_ENTRY Entry; for (Entry = LinkedList.ListHead.Flink; Entry != &LinkedList.ListHead; Entry = Entry->Flink) { EnQueue( &Queue, HeadOfQueue, Entry->Value ); } } break; default: printf("Illegal command\n"); } } while ( cmd != END_OF_FILE ); return; } COMMAND_TYPE GetNextCommand ( int *Param ) /*++ Routine Description: This routine reads in and deciphers the next input line from stdin. Arguments: Param - An integer supplied by the caller that receives any integer values specified in the command Return Value: COMMAND_TYPE - The command of the input line just read in --*/ { int i; char Str[128]; // // This section reads in the next input line and special cases out the // end of file situation. If we go through this section then Str contains // the complete input line and is null terminated. // for (i = 0; i < 128; i += 1) { Str[i] = getchar(); if ((Str[i] == EOF) || (Str[i] == '\n')) { break; } } if ((Str[i] == EOF)) { return END_OF_FILE; } Str[i] = '\0'; // // Now dechipher the input string. For commnds with number we'll use // scanf and put the value into Parm. For all other we'll use the // strncmp function to find exact matches // // // The basic stack commands // if (sscanf(Str, "new stack of size %d", Param)) { return NEW_STACK; } if (sscanf(Str, "push %d", Param)) { return PUSH_NUMBER; } if (!strncmp(Str, "dump stack", strlen("dump stack"))) { return DUMP_STACK; } if (!strncmp(Str, "push accumulator", strlen("push accumulator"))) { return PUSH_ACCUMULATOR; } if (!strncmp(Str, "top +", strlen("top +"))) { return TOP_PLUS; } if (!strncmp(Str, "top -", strlen("top -"))) { return TOP_MINUS; } if (!strncmp(Str, "top *", strlen("top *"))) { return TOP_TIMES; } if (!strncmp(Str, "top /", strlen("top /"))) { return TOP_DIVIDE; } if (!strncmp(Str, "top", strlen("top"))) { return TOP_EQUAL; } if (!strncmp(Str, "pop +", strlen("pop +"))) { return POP_PLUS; } if (!strncmp(Str, "pop -", strlen("pop -"))) { return POP_MINUS; } if (!strncmp(Str, "pop *", strlen("pop *"))) { return POP_TIMES; } if (!strncmp(Str, "pop /", strlen("pop /"))) { return POP_DIVIDE; } if (!strncmp(Str, "pop", strlen("pop"))) { return POP_EQUAL; } // // The basic queue commands // if (sscanf(Str, "new queue of size %d", Param)) { return NEW_QUEUE; } if (sscanf(Str, "enqueue tail %d", Param)) { return ENQUEUE_TAIL_NUMBER; } if (sscanf(Str, "enqueue head %d", Param)) { return ENQUEUE_HEAD_NUMBER; } if (!strncmp(Str, "dump queue", strlen("dump queue"))) { return DUMP_QUEUE; } if (!strncmp(Str, "enqueue tail accumulator", strlen("enqueue tail accumulator"))) { return ENQUEUE_TAIL_ACCUMULATOR; } if (!strncmp(Str, "enqueue head accumulator", strlen("enqueue head accumulator"))) { return ENQUEUE_HEAD_ACCUMULATOR; } if (!strncmp(Str, "tail +", strlen("tail +"))) { return TAIL_PLUS; } if (!strncmp(Str, "tail -", strlen("tail -"))) { return TAIL_MINUS; } if (!strncmp(Str, "tail *", strlen("tail *"))) { return TAIL_TIMES; } if (!strncmp(Str, "tail /", strlen("tail /"))) { return TAIL_DIVIDE; } if (!strncmp(Str, "tail", strlen("tail"))) { return TAIL_EQUAL; } if (!strncmp(Str, "head +", strlen("head +"))) { return HEAD_PLUS; } if (!strncmp(Str, "head -", strlen("head -"))) { return HEAD_MINUS; } if (!strncmp(Str, "head *", strlen("head *"))) { return HEAD_TIMES; } if (!strncmp(Str, "head /", strlen("head /"))) { return HEAD_DIVIDE; } if (!strncmp(Str, "head", strlen("head"))) { return HEAD_EQUAL; } if (!strncmp(Str, "dequeue tail +", strlen("dequeue tail +"))) { return DEQUEUE_TAIL_PLUS; } if (!strncmp(Str, "dequeue tail -", strlen("dequeue tail -"))) { return DEQUEUE_TAIL_MINUS; } if (!strncmp(Str, "dequeue tail *", strlen("dequeue tail *"))) { return DEQUEUE_TAIL_TIMES; } if (!strncmp(Str, "dequeue tail /", strlen("dequeue tail /"))) { return DEQUEUE_TAIL_DIVIDE; } if (!strncmp(Str, "dequeue tail", strlen("dequeue tail"))) { return DEQUEUE_TAIL_EQUAL; } if (!strncmp(Str, "dequeue head +", strlen("dequeue head +"))) { return DEQUEUE_HEAD_PLUS; } if (!strncmp(Str, "dequeue head -", strlen("dequeue head -"))) { return DEQUEUE_HEAD_MINUS; } if (!strncmp(Str, "dequeue head *", strlen("dequeue head *"))) { return DEQUEUE_HEAD_TIMES; } if (!strncmp(Str, "dequeue head /", strlen("dequeue head /"))) { return DEQUEUE_HEAD_DIVIDE; } if (!strncmp(Str, "dequeue head", strlen("dequeue head"))) { return DEQUEUE_HEAD_EQUAL; } // // The basic linkedlist commands // if (sscanf(Str, "insert front %d", Param)) { return INSERT_FRONT_NUMBER; } if (sscanf(Str, "insert back %d", Param)) { return INSERT_BACK_NUMBER; } if (!strncmp(Str, "new linkedlist", strlen("new linkedlist"))) { return NEW_LINKEDLIST; } if (!strncmp(Str, "dump linkedlist", strlen("dump linkedlist"))) { return DUMP_LINKDLIST; } if (!strncmp(Str, "insert front accumulator", strlen("insert front accumulator"))) { return INSERT_FRONT_ACCUMULATOR; } if (!strncmp(Str, "insert back accumulator", strlen("insert back accumulator"))) { return INSERT_BACK_ACCUMULATOR; } if (!strncmp(Str, "front +", strlen("front +"))) { return FRONT_PLUS; } if (!strncmp(Str, "front -", strlen("front -"))) { return FRONT_MINUS; } if (!strncmp(Str, "front *", strlen("front *"))) { return FRONT_TIMES; } if (!strncmp(Str, "front /", strlen("front /"))) { return FRONT_DIVIDE; } if (!strncmp(Str, "front", strlen("front"))) { return FRONT_EQUAL; } if (!strncmp(Str, "back +", strlen("back +"))) { return BACK_PLUS; } if (!strncmp(Str, "back -", strlen("back -"))) { return BACK_MINUS; } if (!strncmp(Str, "back *", strlen("back *"))) { return BACK_TIMES; } if (!strncmp(Str, "back /", strlen("back /"))) { return BACK_DIVIDE; } if (!strncmp(Str, "back", strlen("back"))) { return BACK_EQUAL; } if (!strncmp(Str, "remove front +", strlen("remove front +"))) { return REMOVE_FRONT_PLUS; } if (!strncmp(Str, "remove front -", strlen("remove front -"))) { return REMOVE_FRONT_MINUS; } if (!strncmp(Str, "remove front *", strlen("remove front *"))) { return REMOVE_FRONT_TIMES; } if (!strncmp(Str, "remove front /", strlen("remove front /"))) { return REMOVE_FRONT_DIVIDE; } if (!strncmp(Str, "remove front", strlen("remove front"))) { return REMOVE_FRONT_EQUAL; } if (!strncmp(Str, "remove back +", strlen("remove back +"))) { return REMOVE_BACK_PLUS; } if (!strncmp(Str, "remove back -", strlen("remove back -"))) { return REMOVE_BACK_MINUS; } if (!strncmp(Str, "remove back *", strlen("remove back *"))) { return REMOVE_BACK_TIMES; } if (!strncmp(Str, "remove back /", strlen("remove back /"))) { return REMOVE_BACK_DIVIDE; } if (!strncmp(Str, "remove back", strlen("remove back"))) { return REMOVE_BACK_EQUAL; } // // The extra credit commands // if (!strncmp(Str, "reverse stack", strlen("reverse stack"))) { return REVERSE_STACK; } if (!strncmp(Str, "reverse queue", strlen("reverse queue"))) { return REVERSE_QUEUE; } if (!strncmp(Str, "reverse linkedlist", strlen("reverse linkedlist"))) { return REVERSE_LINKEDLIST; } if (!strncmp(Str, "copy stack to queue", strlen("copy stack to queue"))) { return COPY_STACK_TO_QUEUE; } if (!strncmp(Str, "copy stack to linkedlist", strlen("copy stack to linkedlist"))) { return COPY_STACK_TO_LINKEDLIST; } if (!strncmp(Str, "copy queue to stack", strlen("copy queue to stack"))) { return COPY_QUEUE_TO_STACK; } if (!strncmp(Str, "copy queue to linkedlist", strlen("copy queue to linkedlist"))) { return COPY_QUEUE_TO_LINKEDLIST; } if (!strncmp(Str, "copy linkedlist to stack", strlen("copy linkedlist to stack"))) { return COPY_LINKEDLIST_TO_STACK; } if (!strncmp(Str, "copy linkedlist to queue", strlen("copy linkedlist to queue"))) { return COPY_LINKEDLIST_TO_QUEUE; } // // Nothing matched so we'll tell our caller that the input line is bad // return ILLEGAL_COMMAND; } void NewStack ( PSTACK Stack, int Size ) /*++ Routine Description: Create a new stack of the specified size Arguments: Stack - Supplies a pointer to the stack being initialized Size - Supplies the number of integers to allocate to the next stack. Return Value: None. --*/ { // // First check it there is a old stack that we need to free up // if (Stack->Array != NULL) { free(Stack->Array); } // // Now allocate a new stack and initialize its state // Stack->Array = (int *)malloc( sizeof(int) * Size ); if (Stack->Array == NULL) { printf( "[%s@%d] malloc error\n", __FILE__, __LINE__ ); return; } Stack->Size = Size; Stack->Top = -1; // // And return to our caller // return; } void DumpStack ( PSTACK Stack ) /*++ Routine Description: Dumps the current contents of a stack to stdout Arguments: Stack - Supplies a pointer to the stack being dumped Return Value: None. --*/ { int i; // // print the dump header, and then loop printing // the stack values from top to bottom // printf("dump of stack of size %d\n", Stack->Size); for (i = Stack->Top; i > -1 ; i -= 1) { printf("stack[%d] = %d", i, Stack->Array[i]); if (i == Stack->Top) { printf(" (top of stack)"); } printf("\n"); } printf("\n"); // // And return to our caller // return; } void PushStack ( PSTACK Stack, int Value ) /*++ Routine Description: Push a new value onto a stack except if the stack is about to overflow Arguments: Stack - Supplies a pointer to the stack being manipulated Value - Supplies the value to push onto the stack Return Value: None. --*/ { // // Check for overflow // if (Stack->Top >= (Stack->Size-1)) { printf("Stack overflow\n"); return; } // // Push on the value // Stack->Array[ ++(Stack->Top) ] = Value; // // And return to our caller // return; } int PopStack ( PSTACK Stack, BOOLEAN RemoveItem ) /*++ Routine Description: Return the current top of the stack and possibly pop it off. If the stack is currently empty then nothing is removed. Arguments: Stack - Supplies a pointer to the stack being manipulated RemoveItem - If true the value is also popped from the stack otherwise the stack is left alone Return Value: int - The top of the stack --*/ { int Value; // // Check for underflow // if (Stack->Top < 0) { printf("Stack underflow\n"); return 0; } // // Get the top of the stack // Value = Stack->Array[ Stack->Top ]; // // See if we should remove it // if (RemoveItem) { Stack->Top -= 1; } // // And return to our caller // return Value; } void ReverseStack ( PSTACK Stack ) /*++ Routine Description: Reverses the contents of a stack Arguments: Stack - Supplies a pointer to the stack being manipulated Return Value: None. --*/ { int i, j; int temp; // // With two indices i and j starting at the bottom and top of the stack // we'll simply swap the stack's array contents until the two meet in the // middle // for (i = 0, j = Stack->Top; i < j; i += 1, j -= 1) { temp = Stack->Array[ i ]; Stack->Array[ i ] = Stack->Array[ j ]; Stack->Array[ j ] = temp; } return; } void NewQueue ( PQUEUE Queue, int Size ) /*++ Routine Description: Create a new queue of the specified size Arguments: Queue - Supplies a pointer to the queue being initialized Size - Supplies the number of integers to allocate to the new queue Return Value: None. --*/ { // // Check if we have an old queue to clean up after // if (Queue->Array != NULL) { free(Queue->Array); } // // Allocate space for the new queue // Queue->Array = (int *)malloc( sizeof(int) * Size ); if (Queue->Array == NULL) { printf( "[%s@%d] malloc error\n", __FILE__, __LINE__ ); return; } // // Because we're using a simple index for the head and tail and // we allow insertion at both ends then to guard against the // values going negative. Then to initialize the empty queue we // simply put head and tail in the middle of a unsigned long. // This gives us 2,147,483,647 inserts on either end before // we overflow or underflow these indices. // Queue->Head = 0x7fffffff; Queue->Tail = 0x7fffffff; Queue->Size = Size; Queue->Count = 0; return; } void DumpQueue ( PQUEUE Queue ) /*++ Routine Description: Dump the contents of a queue to stdout Arguments: Queue - Supplies a pointer to the queue being dumped Return Value: None. --*/ { int i; // // Print the dump header and then loop through the queue printing // items from the head to the tail // printf("dump of queue of size %d head to tail\n", Queue->Size); for (i = 0; i < Queue->Count; i += 1) { printf("%d\n", Queue->Array[(Queue->Head + i) % Queue->Size]); } printf("\n"); // // And return to our caller // return; } void EnQueue ( PQUEUE Queue, QUEUE_END QueueEnd, int Value ) /*++ Routine Description: Add a new element to a queue at either the head of the queue or the tail of the queue. Also check it the queue is already full Arguments: Queue - Supplies a pointer to the queue being manipulated QueueEnd - Specifies which end of the queue to add the element Value - Supplies the value to add to the queue Return Value: None --*/ { // // First check to see if the queue is already full // if (Queue->Count >= Queue->Size) { printf("Queue overflow\n"); return; } // // Bump the count of elements in the queue and then // special case queue of only one element // Queue->Count += 1; if (Queue->Count == 1) { Queue->Array[ 0x7fffffff % Queue->Size ] = Value; Queue->Head = 0x7fffffff; Queue->Tail = 0x7fffffff; return; } // // At this point we know the new element will fit and the // queue has at least one element already in it. So based // on the end we'll put the new element on either the head // of the tail // if (QueueEnd == HeadOfQueue) { Queue->Array[ (--Queue->Head) % Queue->Size ] = Value; } else { Queue->Array[ (++Queue->Tail) % Queue->Size ] = Value; } // // And return to our caller // return; } int DeQueue ( PQUEUE Queue, QUEUE_END QueueEnd, BOOLEAN RemoveItem ) /*++ Routine Description: Return an existing element from either the head or tail end of a queue, and possibly remove the elemnt. Also check if the queue is already empty. Arguments: Queue - Supplies a pointer to the queue being manipulated QueueEnd - Specifies which end of the queue to remove the element RemoveItem - If true the value is also removed from the queue otherwise the queue is left alone Return Value: int - The value at either the head or tail of the queue --*/ { int Value; // // Check for an empty queue // if (Queue->Count <= 0) { printf("Queue underflow\n"); return 0; } // // Get the value to return from either end of the queue and we either // remove the item or leave it alone // if (QueueEnd == HeadOfQueue) { if (RemoveItem) { Queue->Count -= 1; Value = Queue->Array[ (Queue->Head) % Queue->Size ]; Queue->Head++; } else { Value = Queue->Array[ (Queue->Head) % Queue->Size ]; } } else { if (RemoveItem) { Queue->Count -= 1; Value = Queue->Array[ (Queue->Tail) % Queue->Size ]; Queue->Tail--; } else { Value = Queue->Array[ (Queue->Tail) % Queue->Size ]; } } // // And return to our caller // return Value; } void ReverseQueue ( PQUEUE Queue ) /*++ Routine Description: Reverses the contents of a queue Arguments: Queue - Supplies a pointer to the queue being manipulated Return Value: None. --*/ { int i; int temp; // // With one index we'll march through the queue from the head // to half to the tail and swapping items as we go // for (i = 0; i < Queue->Count/2; i += 1) { temp = Queue->Array[(Queue->Head + i) % Queue->Size]; Queue->Array[(Queue->Head + i) % Queue->Size] = Queue->Array[(Queue->Tail - i) % Queue->Size]; Queue->Array[(Queue->Tail - i) % Queue->Size] = temp; } // // And return to our caller // return; } void NewLinkedList ( PLINKED_LIST LinkedList ) /*++ Routine Description: Initialize a new linked list data structure, and possibly free up any old existing linked list elements Arguments: LinkedList - Supplies a pointer to the linked list being initialized Return Value: None --*/ { // // Check to see if the linked list already has some elements that need // to be removed // if (LinkedList->ListHead.Flink != NULL) { while (LinkedList->ListHead.Flink != &LinkedList->ListHead) { RemoveLinkedList( LinkedList, FrontOfLinkedList, TRUE ); } } // // Initialize the linked list // LinkedList->ListHead.Flink = &LinkedList->ListHead; LinkedList->ListHead.Blink = &LinkedList->ListHead; // // And return to our caller // return; } void DumpLinkedList ( PLINKED_LIST LinkedList ) /*++ Routine Description: Dump the current contents of a linked list to stdout Arguments: LinkedList - Supplies a pointer to the linked list to dump Return Value: None. --*/ { PLINKED_LIST_ENTRY Entry; // // Print the dump header and then print the elements in the list // from front to back // printf("dump of linked list front to back\n"); for (Entry = LinkedList->ListHead.Flink; Entry != &LinkedList->ListHead; Entry = Entry->Flink) { printf("%d\n", Entry->Value); } // // And return to our caller // return; } void InsertLinkedList ( PLINKED_LIST LinkedList, LINKED_LIST_END LinkedListEnd, int Value ) /*++ Routine Description: Insert a new element into a linked list at either the front or back Arguments: LinkedList - Supplies a pointer to the linked list being manipulated LinkedListEnd - Specifies which end of the list to manipulate Value - Supplies the integer to add to the list Return Value: None --*/ { PLINKED_LIST_ENTRY Entry; // // First allocate a new entry to the linked list // Entry = (PLINKED_LIST_ENTRY)malloc( sizeof(LINKED_LIST_ENTRY) ); if (Entry == NULL) { printf( "[%s@%d] malloc error\n", __FILE__, __LINE__ ); return; } // // Now based on what the caller specified we'll insert it either // at the front or back // if (LinkedListEnd == FrontOfLinkedList) { Entry->Flink = LinkedList->ListHead.Flink; Entry->Blink = &LinkedList->ListHead; } else { Entry->Blink = LinkedList->ListHead.Blink; Entry->Flink = &LinkedList->ListHead; } // // The element points to where it should be now update its // neighbors to point to it // Entry->Flink->Blink = Entry; Entry->Blink->Flink = Entry; // // Set the data in the new item // Entry->Value = Value; // // And return to our caller // return; } int RemoveLinkedList ( PLINKED_LIST LinkedList, LINKED_LIST_END LinkedListEnd, BOOLEAN RemoveItem ) /*++ Routine Description: Return the current value at either end of a linked list and also possibly remove the item Arguments: LinkedList - Supplies a pointer to the linked list being manipulated LinkedListEnd - Specifies which end of the list to manipulate RemoveItem - If true the value is also removed from the list otherwise the list is left alone Return Value: None --*/ { PLINKED_LIST_ENTRY Entry; int Value; // // First check if the list is already empty // if (LinkedList->ListHead.Flink == &LinkedList->ListHead) { printf("LinkedList Underflow\n"); return 0; } // // Now identify the item we're interested in look at, based on // what the caller wanted // if (LinkedListEnd == FrontOfLinkedList) { Entry = LinkedList->ListHead.Flink; } else { Entry = LinkedList->ListHead.Blink; } // // We now have the item so we can get its value // Value = Entry->Value; // // And if the we to remove the item we can now remove it. Note // that removal at this point doesn't matter where in the list the // element is // if (RemoveItem) { Entry->Flink->Blink = Entry->Blink; Entry->Blink->Flink = Entry->Flink; free(Entry); } // // And return to our caller // return Value; } void ReverseLinkedList ( PLINKED_LIST LinkedList ) /*++ Routine Description: Reverses the contents of a linked list Arguments: LinkedList - Supplies a pointer to the linked list being manipulated Return Value: None. --*/ { PLINKED_LIST_ENTRY FrontEntry; PLINKED_LIST_ENTRY BackEntry; int temp; // // With two pointers we'll march front the front and back of the linked // list swapping elements. We'll stop when the pointers cross // FrontEntry = LinkedList->ListHead.Flink; BackEntry = LinkedList->ListHead.Blink; // // If the pointers are equal to each other then we can stop // while (FrontEntry != BackEntry) { // // Do the swap // temp = FrontEntry->Value; FrontEntry->Value = BackEntry->Value; BackEntry->Value = temp; // // Advance one of the pointers and if it now matches the other we can // stop, otherwise we advance the second pointer // FrontEntry = FrontEntry->Flink; if (FrontEntry == BackEntry) { break; } BackEntry = BackEntry->Blink; } // // And return to our caller // return; }